import java.util.HashSet;

public class Leecode141 {

    /**
     * Definition for singly-linked list.
     * class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    public static class Solution {
        public boolean hasCycle(ListNode head) {
           //判断环形链表(使用HashSet完成)
            //set是无序的！！！
            HashSet<ListNode> listNodes = new HashSet<>();
            while (head != null){
                //因为Set是去重的，当Set中元素与循环得到的链表元素相等时，返回ture说中此时有环行链表出现
                if(!listNodes.add(head)){
                    return true;
                }

                head = head.next;
            }
             return  false;
            /**
             * 使用快慢指针，判断更加快速
             *
             *      if(head==null||head.next==null){
             *         return false;
             *      }
             *
             *       ListNode fast = head.next;
             *       ListNode slow = head;
             *
             *       while (fast != slow){
             *         if(fast ==null||fast.next==null){
             *             return false;
             *         }
             *          slow = slow.next;
             *          fast = fast.next.next;
             *       }
             *       return true;
             */
        }
    }

    public static void main(String[] args) {
        // Example 1: No cycle
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(2);
        head1.next.next = new ListNode(3);
        head1.next.next.next = new ListNode(4);
        head1.next.next.next.next = null; // No cycle
        System.out.println("Has cycle in Example 1: " + new Solution().hasCycle(head1));

        // Example 2: Cycle exists
        ListNode head2 = new ListNode(1);
        head2.next = new ListNode(2);
        head2.next.next = new ListNode(3);
        head2.next.next.next = new ListNode(4);
        head2.next.next.next.next = head2.next; // Cycle: 4 -> 2
        System.out.println("Has cycle in Example 2: " + new Solution().hasCycle(head2));
    }
}
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}
